_Algorithms_

Originally, the word algorithm (in its older form, "algorism") meant a
method for doing arithmetic using Arabic numerals; the word came from the
name of al-Khowarizmi, a ninth century Arabic mathematician and textbook
author [Knuth].  It has come to mean any completely specified rule for
processing information.  Carrying out an algorithm requires no imagination,
nor any understanding of the significance of the computation.  Before the
advent of the computer, huge teams of clerks were used to calculate tables
of logarithms and trigonometric functions, tables giving correct angles for
aiming artillery taking account of distance and wind, etc.  Probably few of
them understood the reasons for the algorithms.  Now we tend to relegate
such algorithms to electronic computers, as we shall see.

Most of us have forgotten how complicated the complete algorithms for
arithmetic are.  Here is one such algorithm, to subtract B from A, giving a
result C, where A and B must both be whole numbers (integers), and A must
be greater than B.

(1).  Look up the rightmost digits of A and B in Table 1.
						
						Table 1

					A\B 0   1   2   3   4   5
					---------------------------
					0 | 0   9B  8B  7B  6B  5B
					  |
					1 | 1   0   9B  8B  7B  6B
					  |
					2 | 2   1   0   9B  8B  7B
					  |
					3 | 3   2   1   0   9B  8B
					  |
					4 | 4   3   2   1   0   9B
					  |
					5 | 5   4   3   2   1   0

Write down the digit from the table as the leftmost digit of C.  Remember
whether there was a B ("borrow") at the table entry.  Scratch out the
rightmost digits of A and B.  If there was no borrow, go to step 2;  If
there was a borrow, go to step 3.

(2).  Look up the right most remaining digits of A and B in Table 1.  If A
and B are both used up, you are finished.  If B is used up,  use a zero as
the digit of B.  Write down the end of C.  Remember whether there was a "B"
at the table entry.  Scratch out the rightmost remaining digits of A and
B, if any.  

If there was no borrow, start step 2 again; If there was a borrow, go to
step 3.  Step 3 is just like step 2, except that it uses Table 2, not Table 1.
					
						Table 2

					A\B 0   1   2   3   4 
					----------------------
					0 | 9B  8B  7B  6B  5B
					  |
					1   0   9B  8B  7B  6B
					  |
					2 | 1   0   9B  8B  7B
					  |
					3 | 2   1   0   9B  8B
					  |
					4 | 3   2   1   0   9B

			A		B		C		Borrow
Initially		9053		72            nothing

After Step 1		 905		 7		1		No

After Step 2		  90		gone		81		Yes

After Step 3		   9		gone		981		Yes

After Step 3		gone		gone		8981		No

Finished.

	A Case History:  The Subtraction Algorithm at work.

Most of you, at some time in your lives, learned to count.  In fact, you probably
learned to count starting with any given number; you had an algorithm which,
given a number, would find the number one greater.  For small numbers, you could
do this in your head without strain.

When you learned to add, part of the problem was correct handling of carries.
When you add the hundreds digits of two numbers, by mentally looking the pair up
in a table of the sums of one-digit numbers, you must also remember whether there
was a carry (always a 1, if so) fromthe tens digits.  If there was a carry, you
use your counting algorithm to get the next number larger than the one in the 
addition table.  In order to carry out the addition algorithm, you must first know
the counting algorithm.  In the same way, to multiply, you must know and use an
addition algorithm at several stages.  This pattern is frequent in the contraction
of algorithms; the complex ones are based on the use of simpler ones.  An algorithm
in another algorithm is called subalgorithm of the other algorithm, or a procedure.

_Exercise_

Write out in full the algorithm you use to perform long division.

The standard algorithm for multiplication uses, at certain steps, an algorithm for
addition to add up the partial products.  Algorithms to add and subtract
numbers with a decimal point use an algorithm for lining up decimal points.
The design and documentation of algorithms is often simplified by referring
to already-established algorithms.  

Exercise:  give algorithm for halving.  Observe that to execute such an
algorithm, you must remember your place in the master algorithm while you
carry out the subordinate one.)